Search Results

Documents authored by Schmidt, Marie

Document
DOI: 10.4230/OASIcs.ATMOS.2023.8
Fewer Trains for Better Timetables: The Price of Fixed Line Frequencies in the Passenger-Oriented Timetabling Problem

Authors: Pedro José Correia Duarte, Marie Schmidt, Dennis Huisman, and Lucas P. Veelenturf

Published in: OASIcs, Volume 115, 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)

Abstract
This paper introduces the Passenger-Oriented Timetabling problem with flexible frequencies (POT-flex) in the context of railway planning problems. POT-flex aims at creating feasible railway timetables minimising total perceived passenger travel time. The contribution of the POT-flex lies in its relaxation of the generally adopted assumption that line frequencies should be a fixed part of the input. Instead, we consider flexible line frequencies, encompassing a minimum and maximum frequency per line, allowing the timetabling model to decide on optimal line frequencies to obtain better solutions using fewer train services per line. We develop a mixed-integer programming formulation for POT-flex based on the Passenger-Oriented Timetabling (POT) formulation of [Polinder et al., 2021] and compare the performance of the new formulation against the POT formulation on three instances. We find that POT-flex allows to find feasible timetables in instances containing bottlenecks, and show improvements of up to 2% on the largest instance tested. These improvements highlight the cost that fixed line frequencies can have on timetabling.
Cite as

Pedro José Correia Duarte, Marie Schmidt, Dennis Huisman, and Lucas P. Veelenturf. Fewer Trains for Better Timetables: The Price of Fixed Line Frequencies in the Passenger-Oriented Timetabling Problem. In 23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023). Open Access Series in Informatics (OASIcs), Volume 115, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{correiaduarte_et_al:OASIcs.ATMOS.2023.8,
  author =	{Correia Duarte, Pedro Jos\'{e} and Schmidt, Marie and Huisman, Dennis and Veelenturf, Lucas P.},
  title =	{{Fewer Trains for Better Timetables: The Price of Fixed Line Frequencies in the Passenger-Oriented Timetabling Problem}},
  booktitle =	{23rd Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2023)},
  pages =	{8:1--8:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-302-7},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{115},
  editor =	{Frigioni, Daniele and Schiewe, Philine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2023.8},
  URN =		{urn:nbn:de:0030-drops-187695},
  doi =		{10.4230/OASIcs.ATMOS.2023.8},
  annote =	{Keywords: PESP, Passenger Oriented Timetabling, Perceived Travel Time}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2020.15
A Rolling Horizon Heuristic with Optimality Guarantee for an On-Demand Vehicle Scheduling Problem

Authors: Johann Hartleb and Marie Schmidt

Published in: OASIcs, Volume 85, 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)

Abstract
We consider a basic vehicle scheduling problem that arises in the context of travel demand models: Given demanded vehicle trips, what is the minimal number of vehicles needed to fulfill the demand? In this paper, we model the vehicle scheduling problem as a network flow problem. Since instances arising in the context of travel demand models are often so big that the network flow model becomes intractable, we propose using a rolling horizon heuristic to split huge problem instances into smaller subproblems and solve them independently to optimality. By letting the horizons of the subproblems overlap, it is possible to look ahead to the demand of the next subproblem. We prove that composing the solutions of the subproblems yields an optimal solution to the whole problem if the overlap of the horizons is sufficiently large. Our experiments show that this approach is not only suitable for solving extremely large instances that are intractable as a whole, but it is also possible to decrease the solution time for large instances compared to a comprehensive approach.
Cite as

Johann Hartleb and Marie Schmidt. A Rolling Horizon Heuristic with Optimality Guarantee for an On-Demand Vehicle Scheduling Problem. In 20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020). Open Access Series in Informatics (OASIcs), Volume 85, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{hartleb_et_al:OASIcs.ATMOS.2020.15,
  author =	{Hartleb, Johann and Schmidt, Marie},
  title =	{{A Rolling Horizon Heuristic with Optimality Guarantee for an On-Demand Vehicle Scheduling Problem}},
  booktitle =	{20th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2020)},
  pages =	{15:1--15:18},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-170-2},
  ISSN =	{2190-6807},
  year =	{2020},
  volume =	{85},
  editor =	{Huisman, Dennis and Zaroliagis, Christos D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2020.15},
  URN =		{urn:nbn:de:0030-drops-131513},
  doi =		{10.4230/OASIcs.ATMOS.2020.15},
  annote =	{Keywords: Rolling Horizon Heuristic, Vehicle Scheduling, Network Flow}
}
Document
Complete Volume
DOI: 10.4230/OASIcs.ATMOS.2015
OASIcs, Volume 48, ATMOS'15, Complete Volume

Authors: Giuseppe F. Italiano and Marie Schmidt

Published in: OASIcs, Volume 48, 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)

Abstract
OASIcs, Volume 48, ATMOS'15, Complete Volume
Cite as

15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015). Open Access Series in Informatics (OASIcs), Volume 48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Proceedings{italiano_et_al:OASIcs.ATMOS.2015,
  title =	{{OASIcs, Volume 48, ATMOS'15, Complete Volume}},
  booktitle =	{15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-99-6},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{48},
  editor =	{Italiano, Giuseppe F. and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2015},
  URN =		{urn:nbn:de:0030-drops-54712},
  doi =		{10.4230/OASIcs.ATMOS.2015},
  annote =	{Keywords: Analysis of Algorithms and Problem Complexity, Optimization, Combinatorics, Graph Theory, Applications}
}
Document
Front Matter
DOI: 10.4230/OASIcs.ATMOS.2015.i
Front Matter, Table of Contents, Preface, Organization

Authors: Giuseppe F. Italiano and Marie Schmidt

Published in: OASIcs, Volume 48, 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)

Abstract
Front Matter, Table of Contents, Preface, Organization
Cite as

15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015). Open Access Series in Informatics (OASIcs), Volume 48, pp. i-x, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{italiano_et_al:OASIcs.ATMOS.2015.i,
  author =	{Italiano, Giuseppe F. and Schmidt, Marie},
  title =	{{Front Matter, Table of Contents, Preface, Organization}},
  booktitle =	{15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015)},
  pages =	{i--x},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-99-6},
  ISSN =	{2190-6807},
  year =	{2015},
  volume =	{48},
  editor =	{Italiano, Giuseppe F. and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2015.i},
  URN =		{urn:nbn:de:0030-drops-54505},
  doi =		{10.4230/OASIcs.ATMOS.2015.i},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Organization}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2013.1
Recoverable Robust Timetable Information

Authors: Marc Goerigk, Sacha Heße, Matthias Müller-Hannemann, Marie Schmidt, and Anita Schöbel

Published in: OASIcs, Volume 33, 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2013)

Abstract
Timetable information is the process of determining a suitable travel route for a passenger. Due to delays in the original timetable, in practice it often happens that the travel route cannot be used as originally planned. For a passenger being already en route, it would hence be useful to know about alternatives that ensure that his/her destination can be reached. In this work we propose a recoverable robust approach to timetable information; i.e., we aim at finding travel routes that can easily be updated when delays occur during the journey. We present polynomial-time algorithms for this problem and evaluate the performance of the routes obtained this way on schedule data of the German train network of 2013 and simulated delay scenarios.
Cite as

Marc Goerigk, Sacha Heße, Matthias Müller-Hannemann, Marie Schmidt, and Anita Schöbel. Recoverable Robust Timetable Information. In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{goerigk_et_al:OASIcs.ATMOS.2013.1,
  author =	{Goerigk, Marc and He{\ss}e, Sacha and M\"{u}ller-Hannemann, Matthias and Schmidt, Marie and Sch\"{o}bel, Anita},
  title =	{{Recoverable Robust Timetable Information}},
  booktitle =	{13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{1--14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-58-3},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{33},
  editor =	{Frigioni, Daniele and Stiller, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013.1},
  URN =		{urn:nbn:de:0030-drops-42407},
  doi =		{10.4230/OASIcs.ATMOS.2013.1},
  annote =	{Keywords: timetable information, recoverable robustness, delay scenarios}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2011.76
The Price of Robustness in Timetable Information

Authors: Marc Goerigk, Martin Knoth, Matthias Müller-Hannemann, Marie Schmidt, and Anita Schöbel

Published in: OASIcs, Volume 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2011)

Abstract
In timetable information in public transport the goal is to search for a good passenger's path between an origin and a destination. Usually, the travel time and the number of transfers shall be minimized. In this paper, we consider robust timetable information, i.e. we want to identify a path which will bring the passenger to the planned destination even in the case of delays. The classic notion of strict robustness leads to the problem of identifying those changing activities which will never break in any of the expected delay scenarios. We show that this is in general a strongly NP-hard problem. Therefore, we propose a conservative heuristic which identifies a large subset of these robust changing activities in polynomial time by dynamic programming and so allows us to find strictly robust paths efficiently. We also transfer the notion of light robustness, originally introduced for timetabling, to timetable information. In computational experiments we then study the price of strict and light robustness: How much longer is the travel time of a robust path than of a shortest one according to the published schedule? Based on the schedule of high-speed trains within Germany of 2011, we quantitatively explore the trade-off between the level of guaranteed robustness and the increase in travel time. Strict robustness turns out to be too conservative, while light robustness is promising: a modest level of guarantees is achievable at a reasonable price for the majority of passengers.
Cite as

Marc Goerigk, Martin Knoth, Matthias Müller-Hannemann, Marie Schmidt, and Anita Schöbel. The Price of Robustness in Timetable Information. In 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, pp. 76-87, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{goerigk_et_al:OASIcs.ATMOS.2011.76,
  author =	{Goerigk, Marc and Knoth, Martin and M\"{u}ller-Hannemann, Matthias and Schmidt, Marie and Sch\"{o}bel, Anita},
  title =	{{The Price of Robustness in Timetable Information}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{76--87},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{20},
  editor =	{Caprara, Alberto and Kontogiannis, Spyros},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2011.76},
  URN =		{urn:nbn:de:0030-drops-32680},
  doi =		{10.4230/OASIcs.ATMOS.2011.76},
  annote =	{Keywords: strict and light robustness, delay scenarios, experimental study}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2011.88
Delay Management including Capacities of Stations

Authors: Twan Dollevoet, Marie Schmidt, and Anita Schöbel

Published in: OASIcs, Volume 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2011)

Abstract
The question of delay management (DM) is whether trains should wait for delayed feeder trains or should depart on time. Solutions to this problem strongly depend on the capacity constraints of the tracks making sure that no two trains can use the same piece of track at the same time. While these capacity constraints have been included in integer programming formulations for DM, the capacity constraints of the stations (only offering a limited number of platforms) have been neglected so far. This can lead to highly infeasible solutions. In order to overcome this problem we suggest two new formulations for DM both including the stations' capacities. We present numerical results showing that the assignment-based formulation is clearly superior to the packing formulation. We furthermore propose an iterative algorithm in which we improve the platform assignment with respect to the current delays of the trains at each station in each step. We will show that this subproblem asks for coloring the nodes of a graph with a given number of colors while minimizing the weight of the conflicts. We show that the graph to be colored is an interval graph and that the problem can be solved in polynomial time by presenting a totally unimodular IP formulation.
Cite as

Twan Dollevoet, Marie Schmidt, and Anita Schöbel. Delay Management including Capacities of Stations. In 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, pp. 88-99, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{dollevoet_et_al:OASIcs.ATMOS.2011.88,
  author =	{Dollevoet, Twan and Schmidt, Marie and Sch\"{o}bel, Anita},
  title =	{{Delay Management including Capacities of Stations}},
  booktitle =	{11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{88--99},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-33-0},
  ISSN =	{2190-6807},
  year =	{2011},
  volume =	{20},
  editor =	{Caprara, Alberto and Kontogiannis, Spyros},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2011.88},
  URN =		{urn:nbn:de:0030-drops-32699},
  doi =		{10.4230/OASIcs.ATMOS.2011.88},
  annote =	{Keywords: Delay management, station capacities}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2010.156
The Complexity of Integrating Routing Decisions in Public Transportation Models

Authors: Marie Schmidt and Anita Schöbel

Published in: OASIcs, Volume 14, 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10) (2010)

Abstract
To model and solve optimization problems arising in public transportation, data about the passengers is necessary and has to be included in the models in any phase of the planning process. Many approaches assume a two-step procedure: in a first step, the data about the passengers is distributed over the public transportation network using traffic-assignment procedures. In a second step, the actual planning of lines, timetables, etc. takes place. This approach ignores that for most passengers there are many possible ways to reach their destinations in the public transportation network, thus the actual connections the passengers will take depend strongly on the decisions made during the planning phase. In this paper we investigate the influence of integrating the traffic assignment procedure in the optimization process on the complexity of line planning and aperiodic timetabling. In both problems, our objective is to maximize the passengers' benefit, namely to minimize the overall travel time of the passengers in the network. We present new models, analyze NP-hardness results arising from the integration of the routing decisions in the traditional models, and derive polynomial algorithms for special cases.
Cite as

Marie Schmidt and Anita Schöbel. The Complexity of Integrating Routing Decisions in Public Transportation Models. In 10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10). Open Access Series in Informatics (OASIcs), Volume 14, pp. 156-169, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{schmidt_et_al:OASIcs.ATMOS.2010.156,
  author =	{Schmidt, Marie and Sch\"{o}bel, Anita},
  title =	{{The Complexity of Integrating Routing Decisions in Public Transportation Models}},
  booktitle =	{10th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS'10)},
  pages =	{156--169},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-20-0},
  ISSN =	{2190-6807},
  year =	{2010},
  volume =	{14},
  editor =	{Erlebach, Thomas and L\"{u}bbecke, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2010.156},
  URN =		{urn:nbn:de:0030-drops-27575},
  doi =		{10.4230/OASIcs.ATMOS.2010.156},
  annote =	{Keywords: Line Planning, Timetabling, Routing}
}
Document
DOI: 10.4230/OASIcs.ATMOS.2009.2143
Delay Management with Re-Routing of Passengers

Authors: Twan Dollevoet, Dennis Huisman, Marie Schmidt, and Anita Schoebel

Published in: OASIcs, Volume 12, 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09) (2009)

Abstract
Trains often arrive delayed at stations where passengers have to change to other trains. The question of delay management is whether these trains should wait for the original train or depart on time. In traditional delay management models passengers always take their originally planned route. This means, they are in case of a missed connection always delayed with the cycle time of the timetable. In this paper, we propose a model where re-routing of passengers is incorporated. \\ To describe the problem we represent it as an event-activity network similar to the one used in traditional delay management, with some additional events to incorporate origin and destination of the passengers. We prove NP-hardness of this problem, and we present an integer programming formulation for which we report the first numerical results. Furthermore, we discuss the variant in which we assume fixed costs for maintaining transfers and we present a polynomial algorithm for the special case of only one origin-destination pair.
Cite as

Twan Dollevoet, Dennis Huisman, Marie Schmidt, and Anita Schoebel. Delay Management with Re-Routing of Passengers. In 9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09). Open Access Series in Informatics (OASIcs), Volume 12, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{dollevoet_et_al:OASIcs.ATMOS.2009.2143,
  author =	{Dollevoet, Twan and Huisman, Dennis and Schmidt, Marie and Schoebel, Anita},
  title =	{{Delay Management with Re-Routing of Passengers}},
  booktitle =	{9th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS'09)},
  pages =	{1--17},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-11-8},
  ISSN =	{2190-6807},
  year =	{2009},
  volume =	{12},
  editor =	{Clausen, Jens and Di Stefano, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2009.2143},
  URN =		{urn:nbn:de:0030-drops-21433},
  doi =		{10.4230/OASIcs.ATMOS.2009.2143},
  annote =	{Keywords: Transportation, Delay Management, Re-Routing, OD-pairs Transportation, Delay Management, Re-Routing, OD-pairs}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact